package com.zpself.module.算法练习.算法;

/**
 * @author By ZengPeng
 * @Description 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
 *               给定一个数字 n，找出可形成完整阶梯行的总行数。
 *               n 是一个非负整数，并且在32位有符号整型的范围内。
 *
 *               其实就是：给定整数n，求[1,k]（k为整数）之间满足1+2+3+4...+k<=n的最大k值。
 * @date in  2021/1/20 19:13
 * @Modified By
 */
public class 力扣_441_排列硬币 {
    public static void main(String[] args) {
//        System.out.println(myAnswer3(1804289383));
        System.out.println(myAnswer3(1681692777));
//        System.out.println(myAnswer3(1));
//        System.out.println(myAnswer3(8));
//        System.out.println(myAnswer3(12));
    }

    public  static  int myAnswer(int n){
        int j= 0 ;
        while (n>j){
            j++;
            n -=j;
        }
        return j;
    }

    public  static  int myAnswer2(int n){
        return (int) (-1 + Math.sqrt(1 + 8 * (long) n)) / 2;
    }


    //自己想的方法：(k+1)*k/2   <  n   <   (k+2)*(k+1) /2
    //所以    k*k/2  < n
    //所以    k < log 2n
    //所以   从k  = log 2n -1  开始遍历相减
    public  static  int myAnswer3(int n){
        int k = (int)Math.sqrt(2L*n) -1;
        int sum= (int) ((k+1L)*k/2);
        n= n-sum;
        while (n>k){
            k++;
            n-=k;
        }
        return k;
    }
}
